﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
//Top--k问题: 求n个数据中前k个最小值或者最大值,通常n>>k
/*
以求n个数据中前k个最大值为例
解决思路:
首先将n个数据中的前k个数据建成大堆,再遍历后面的n-k个数据，
接着逐个与堆顶数据比较，如果比堆顶数据小，就与堆顶数据交换位置，如果比堆顶数据大，就继续向后遍历
*/
void Swap(int* x, int* y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}


//向下调整算法建堆(以建小堆为例)
void AdjustDown(int* arr, int parent, int n)
{
	assert(arr);
	//先根据父结点的下标parent，求左孩子结点的下标child
	int child = 2 * parent + 1;
	//再找左、右孩子中存储的值较小的结点，将该结点与父结点中的值进行比较，若该结点中的值更小，就交换这两个结点
	while (child < n)//孩子结点的下标child最大为n-1，不能越界
	{
		//根据左孩子的下标child可知，右孩子的下标是child+1
		//有可能父结点没有右孩子，因此要保证child+1不能越界，即child + 1 < n
		if (child + 1 < n && arr[child + 1] < arr[child])
		{
			child++;
		}
		//此时child一定是左、右孩子中，存储的值较小的结点的下标
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			//交换之后，再更新parent与child的值
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}


// 造数据
void CreateNDate()
{
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void topk()
{
	printf("请输入k: ");
	int k = 0;
	scanf("%d", &k);
	const char * file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		exit(1);
	}
	int val = 0;
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		exit(2);
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}
	// 建k个数据的⼩堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, i, k);
	}
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		// 读取剩余数据，⽐堆顶的值⼤，就替换他进堆       
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, 0, k);

		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}


int main()
{
	//CreateNDate();
	topk();
	return 0;
}








